package com.heima.algorithm.dynamicprogramming;

/**
 * 钢条切割问题
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/11 14:34
 */
public class CutRodProblem {
    /*
        0   1   2   3   4   5   6   7   8   9   10   长度
        0   1   5   8   9   10  17  17  20  24  30   价格

        问现有5m的钢条，怎么切割收益最大？
            0    1    2    3    4    5   总长度
        1   0    1    11   111  1111 11111
           (0)  (1)   (2)  (3)   (4)  (5)

        2   0    1    11   111  1111 11111
                      2    21   211  2111
                                22   221
           (0)  (1)   (5)  (6)  (10) (11)

        3   0    1    11   111  1111 11111
                      2    21   211  2111
                           3    22   221
                                31   311
                                     32
           (0)  (1)   (5)  (8)  (10) (13)

        4   0    1    11   111  1111 11111
                      2    21   211  2111
                           3    22   221
                                31   311
                                4    32
                                     41
           (0)  (1)   (5)  (8)  (10) (13)

        5   0    1    11   111  1111 11111
                      2    21   211  2111
                           3    22   221
                                31   311
                                4    32
                                     41
                                     5
           (0)  (1)   (5)  (8)  (10) (13)
   考虑切割长度

      以上括号内的内容是此动态数组记录的内容，也就是说dp[i][j]表示综合前面0-i
      种切割方案去切割长度为j的钢条所能获得的最大价值

      if(当前切割方案的长度大于钢条总长度){
          dp[i][j] = dp[i-1][j];
      }else{
          dp[i][j] = max(dp[i-1][j], price[i] + dp[i][j-i]) // 这里i是也是指切割方案的长度
      }
     */

    public static int cutRod(int[] prices, int n) {
        int[][] dp = new int[prices.length][n + 1];
        for (int j = 1; j <= n; j++){
            if (j >= 1){
                dp[1][j] = prices[1] + dp[1][j - 1];
            }
        }
        for (int i = 2; i < prices.length; i++){
            for (int j = 1; j <= n; j++){
                if (j >= i){
                    dp[i][j] = Math.max(dp[i - 1][j], prices[i] + dp[i][j - i]);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[prices.length - 1][n];
    }

    public static void main(String[] args) {
        int[] prices = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        int n = 5;
        System.out.println(cutRod(prices, n));
    }
}
